package demo.practice.bfs;


import java.util.LinkedList;
import java.util.Queue;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

public class P116 {

        public Node connect(Node root) {


            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                int len = queue.size();
                Node befor = null;
                while (len > 0) {
                    Node poll = queue.poll();
                    if (befor != null)
                        befor.next = poll;

                    if (poll.left != null)
                        queue.add(poll.left);

                    if (poll.right != null)
                        queue.add(poll.right);
                    befor =poll;
                    len--;
                }

            }
            return root;
        }
}
